{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Price to Fill a Bag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #填满背包的最大价格"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二维整数数组 <code>items</code> ，其中 <code>items[i] = [price<sub>i</sub>, weight<sub>i</sub>]</code> 表示第 <code>i</code> 个物品的价格和重量。</p>\n",
    "\n",
    "<p>还给定一个 <strong>正</strong> 整数容量 <code>capacity</code> 。</p>\n",
    "\n",
    "<p>每个物品可以分成两个部分，比率为 <code>part1</code> 和 <code>part2</code> ，其中 <code>part1 + part2 == 1</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第一个物品的重量是 <code>weighti * part1</code> ，价格是 <code>pricei * part1</code> 。</li>\n",
    "\t<li>同样，第二个物品的重量是 <code>weighti * part2</code>&nbsp;，价格是 <code>pricei * part2</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>使用给定的物品，返回填满容量为 <code>capacity</code> 的背包所需的 <strong>最大总价格</strong> 。如果无法填满背包，则返回 <code>-1</code> 。与实际答案的差距在&nbsp;<code>10<sup>-5</sup></code>&nbsp;以内的 <strong>实际答案</strong> 将被视为接受。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>items = [[50,1],[10,8]], capacity = 5\n",
    "<b>输出：</b>55.00000\n",
    "<b>解释：</b>\n",
    "我们将第二个物品分成两个部分，part1 = 0.5，part2 = 0.5。 \n",
    "第一个物品的价格和重量分别为 5 和 4 。同样地，第二个物品的价格和重量也是 5 和 4 。 \n",
    "经过操作后，数组 items 变为 [[50,1],[5,4],[5,4]] 。 \n",
    "为了填满容量为 5 的背包，我们取价格为 50 的第一个元素和价格为 5 的第二个元素。 \n",
    "可以证明，55.0 是我们可以达到的最大总价值。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>items = [[100,30]], capacity = 50\n",
    "<b>输出：</b>-1.00000\n",
    "<b>解释：</b>无法用给定的物品装满背包。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= items.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>items[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= price<sub>i</sub>, weight<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= capacity &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-price-to-fill-a-bag](https://leetcode.cn/problems/maximum-price-to-fill-a-bag/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-price-to-fill-a-bag](https://leetcode.cn/problems/maximum-price-to-fill-a-bag/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[50,1],[10,8]]\\n5', '[[100,30]]\\n50']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        new_items = sorted([[item[0]/item[1],item[0],item[1]] for item in items],reverse = True)\n",
    "\n",
    "        ans = 0\n",
    "        for _, value, weight in new_items:\n",
    "            if capacity >= weight:\n",
    "                ans += value\n",
    "                capacity -= weight\n",
    "            else:\n",
    "                ans += value * (capacity / weight)\n",
    "                capacity -= capacity\n",
    "                break\n",
    "\n",
    "        if capacity:\n",
    "            return -1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        if sum(w for _, w in items) < capacity:\n",
    "            return -1\n",
    "        items.sort(key = lambda x: x[0]/x[1], reverse=True)\n",
    "        remain = capacity\n",
    "        val = 0\n",
    "        for p, w in items:\n",
    "            if remain <= 0:\n",
    "                return val\n",
    "            if w <= remain:\n",
    "                remain -= w\n",
    "                val += p\n",
    "            else:\n",
    "                val += remain/w * p\n",
    "                remain = 0\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], cap: int) -> float:\n",
    "        if sum(w for p,w in items) < cap:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        items.sort(key = lambda x:-(x[0] / x[1]))\n",
    "        l,n = 0,len(items)\n",
    "        while l < n:\n",
    "            if items[l][1] <= cap:\n",
    "                ans += items[l][0]\n",
    "                cap -= items[l][1]\n",
    "                l += 1\n",
    "            else:\n",
    "                ans += items[l][0] / items[l][1] * cap\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        # Calculate price/weight ratio for each item and sort based on the ratio in descending order\n",
    "        sorted_items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)\n",
    "        \n",
    "        totalPrice = 0.0\n",
    "        for price, weight in sorted_items:\n",
    "            if capacity >= weight:\n",
    "                totalPrice += price\n",
    "                capacity -= weight\n",
    "            else:\n",
    "                fraction = capacity / weight\n",
    "                totalPrice += fraction * price\n",
    "                capacity = 0\n",
    "            # If the bag is full, break\n",
    "            if capacity == 0:\n",
    "                break\n",
    "\n",
    "        # If bag is not full after considering all items, return -1\n",
    "        if capacity != 0:\n",
    "            return -1.0\n",
    "        \n",
    "        return totalPrice\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        if sum(w for p,w in items) <capacity:\n",
    "            return -1\n",
    "        ans=0\n",
    "        items.sort(key=lambda x:-(x[0]/x[1]))\n",
    "        l,n=0,len(items)\n",
    "        while l<n:\n",
    "            if items[l][1]<=capacity:\n",
    "                ans+=items[l][0]\n",
    "                capacity-=items[l][1]\n",
    "                l+=1\n",
    "            else:\n",
    "                ans+=items[l][0]/items[l][1]*capacity\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        sorted_items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)\n",
    "        \n",
    "        totalPrice = 0.0\n",
    "        \n",
    "        for price, weight in sorted_items:\n",
    "            if capacity == 0:\n",
    "                break\n",
    "            # Determine the amount of the item we can take\n",
    "            amount = min(weight, capacity)\n",
    "            totalPrice += (price / weight) * amount\n",
    "            capacity -= amount\n",
    "        \n",
    "        # If we've exhausted all items and still have capacity left, return -1\n",
    "        if capacity > 0:\n",
    "            return -1.0\n",
    "        \n",
    "        return totalPrice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        items.sort(key=lambda p: -p[0] / p[1])\n",
    "        ans = 0\n",
    "        for p, w in items:\n",
    "            if capacity >= w:\n",
    "                ans += p \n",
    "                capacity -= w\n",
    "            else:\n",
    "                ans += capacity * p / w\n",
    "                capacity = 0\n",
    "            if capacity == 0:\n",
    "                break \n",
    "        if capacity > 0:\n",
    "            return -1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        n = len(items)\n",
    "        items = sorted(items, key = lambda x : -1 * (x[0] / x[1]))\n",
    "        s = ans = 0\n",
    "        for i, (p, w) in enumerate(items):\n",
    "            if s + w <= capacity:\n",
    "                s += w\n",
    "                ans += p\n",
    "            else:\n",
    "                ans += (capacity - s) / w * p\n",
    "                s = capacity\n",
    "                break\n",
    "        return ans if s >= capacity else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        # Calculate price/weight ratio for each item and sort based on the ratio in descending order\n",
    "        sorted_items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)\n",
    "        \n",
    "        totalPrice = 0.0\n",
    "        for price, weight in sorted_items:\n",
    "            if capacity >= weight:\n",
    "                totalPrice += price\n",
    "                capacity -= weight\n",
    "            else:\n",
    "                fraction = capacity / weight\n",
    "                totalPrice += fraction * price\n",
    "                capacity = 0\n",
    "            # If the bag is full, break\n",
    "            if capacity == 0:\n",
    "                break\n",
    "\n",
    "        # If bag is not full after considering all items, return -1\n",
    "        if capacity != 0:\n",
    "            return -1.0\n",
    "        \n",
    "        return totalPrice\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        if sum(x[1] for x in items) < capacity:\n",
    "            return -1\n",
    "        items.sort(key= lambda x:(x[0]/x[1]), reverse=True) \n",
    "        cnt, res = capacity, 0\n",
    "        for i in range(len(items)):\n",
    "            if items[i][1] <= cnt:\n",
    "                res += items[i][0]\n",
    "                cnt -= items[i][1]\n",
    "            else:\n",
    "                res += cnt*(items[i][0]/items[i][1])\n",
    "                break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "\n",
    "        items.sort(key=lambda x:x[1]/x[0])\n",
    "        res = 0\n",
    "        for p,w in items:\n",
    "            if capacity<=w:\n",
    "                res+=capacity * (p/w)\n",
    "                return res\n",
    "            else:\n",
    "                capacity-=w\n",
    "                res += p\n",
    "        return -1 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], cap: int) -> float:\n",
    "        if sum(w for p,w in items) < cap:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        items.sort(key = lambda x:-(x[0] / x[1]))\n",
    "        l,n = 0,len(items)\n",
    "        while l < n:\n",
    "            if items[l][1] <= cap:\n",
    "                ans += items[l][0]\n",
    "                cap -= items[l][1]\n",
    "                l += 1\n",
    "            else:\n",
    "                ans += items[l][0] / items[l][1] * cap\n",
    "                return ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], cap: int) -> float:\n",
    "        if sum(w for p,w in items) < cap:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        items.sort(key = lambda x:-(x[0] / x[1]))\n",
    "        l,n = 0,len(items)\n",
    "        while l < n:\n",
    "            if items[l][1] <= cap:\n",
    "                ans += items[l][0]\n",
    "                cap -= items[l][1]\n",
    "                l += 1\n",
    "            else:\n",
    "                ans += items[l][0] / items[l][1] * cap\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self,items:List[List[int]],capacity:int)->float:\n",
    "        items.sort(key=lambda x:x[1]/x[0])\n",
    "        price=0\n",
    "        for p,c in items:\n",
    "            if c>=capacity:\n",
    "                return price+p*capacity/c\n",
    "            price+=p\n",
    "            capacity-=c\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        if sum(w for _, w in items) < capacity:\n",
    "            return -1\n",
    "        items.sort(key = lambda x: x[0]/x[1], reverse=True)\n",
    "        print(items)\n",
    "        remain = capacity\n",
    "        val = 0\n",
    "        for p, w in items:\n",
    "            if remain <= 0:\n",
    "                return val\n",
    "            if w <= remain:\n",
    "                remain -= w\n",
    "                val += p\n",
    "            else:\n",
    "                val += remain/w * p\n",
    "                remain = 0\n",
    "            print(val)\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        items.sort(key = lambda x: x[1] / x[0])\n",
    "\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "            price += p \n",
    "            capacity -= c \n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        items.sort(key=lambda x: x[0] / x[1], reverse=True)\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "            price += p\n",
    "            capacity -= c\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        items.sort(key=lambda x: x[0] / x[1], reverse=True)\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "            price += p\n",
    "            capacity -= c\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        items.sort(key=lambda x: - x[0]/ x[1])\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "\n",
    "            price += p\n",
    "            capacity -= c\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxPrice(self, items, capacity):\n",
    "        items.sort(key = lambda x: float(x[0]) / float(x[1]), reverse = True)\n",
    "        res = 0\n",
    "        for x, y in items:\n",
    "            if y <= capacity:\n",
    "                res += x\n",
    "                capacity -= y\n",
    "            else:\n",
    "                res += x * float(capacity) / float(y)\n",
    "                capacity = 0\n",
    "                break\n",
    "        return -1 if capacity > 0 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        items.sort(key=lambda x: x[1] / x[0])\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "            price += p\n",
    "            capacity -= c\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "\n",
    "        items.sort(key=lambda x:x[1]/x[0])\n",
    "        res = 0\n",
    "        for p,w in items:\n",
    "            if capacity<=w:\n",
    "                res+=capacity * (p/w)\n",
    "                return res\n",
    "            else:\n",
    "                capacity-=w\n",
    "                res += p\n",
    "        return -1 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "    # Calculate price/weight ratio for each item\n",
    "        ratios = [(price/weight, price, weight, i) for i, (price, weight) in enumerate(items)]\n",
    "        # Sort based on the ratio in descending order\n",
    "        ratios.sort(reverse=True, key=lambda x: x[0])\n",
    "        \n",
    "        totalPrice = 0.0\n",
    "        for ratio, price, weight, _ in ratios:\n",
    "            if capacity >= weight:\n",
    "                totalPrice += price\n",
    "                capacity -= weight\n",
    "            else:\n",
    "                fraction = capacity / weight\n",
    "                totalPrice += fraction * price\n",
    "                capacity = 0\n",
    "            # If the bag is full, break\n",
    "            if capacity == 0:\n",
    "                break\n",
    "\n",
    "        # If bag is not full after considering all items, return -1\n",
    "        if capacity != 0:\n",
    "            return -1.0\n",
    "        \n",
    "        return totalPrice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        h = []\n",
    "        for p, w in items:\n",
    "            heappush(h, (- p / w, p, w))\n",
    "\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        while cur < capacity and h:\n",
    "            _, p, w = heappop(h)\n",
    "            need = capacity - cur\n",
    "            if need >= w:\n",
    "                cur += w\n",
    "                ans += p\n",
    "            else:\n",
    "                ans += p * need / w\n",
    "                cur = capacity\n",
    "                break\n",
    "        return ans if cur == capacity else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        weight = sum([x[1] for x in items])\n",
    "        if weight < capacity:\n",
    "            return -1.0\n",
    "        items.sort(key=lambda x: x[0] / x[1], reverse=True)\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "            price += p\n",
    "            capacity -= c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        weight = sum([x[1] for x in items])\n",
    "        if weight < capacity:\n",
    "            return -1.0\n",
    "        items.sort(key=lambda x: x[0] / x[1], reverse=True)\n",
    "        price = 0\n",
    "        for p, c in items:\n",
    "            if c >= capacity:\n",
    "                return price + p * capacity / c\n",
    "            price += p\n",
    "            capacity -= c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        for i in range(len(items)):\n",
    "            items[i][0] = items[i][0] / items[i][1]\n",
    "        items.sort(key=lambda k: k[0], reverse=True)\n",
    "        items = collections.deque(items)\n",
    "        left = capacity\n",
    "        ans = 0\n",
    "        while left > 0:\n",
    "            if not items:\n",
    "                return -1\n",
    "            p, w = items.popleft()\n",
    "            ans += p * min(left, w)\n",
    "            left -= min(left, w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        d1={}\n",
    "        for i in items:\n",
    "            tmp=i[0]/i[1]\n",
    "            if tmp in d1:\n",
    "                d1[tmp]+=i[1]\n",
    "            else:\n",
    "                d1[tmp]=i[1]\n",
    "        l1=list(d1.keys())\n",
    "        l1.sort(reverse=True)\n",
    "        res=0\n",
    "        for j in l1:\n",
    "            if d1[j]>=capacity:\n",
    "                res+=capacity*j\n",
    "                return res\n",
    "            else:\n",
    "                res+=j*d1[j]\n",
    "                capacity-=d1[j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxPrice(self, items: List[List[int]], capacity: int) -> float:\n",
    "        if np.sum(items,axis=0)[1]<capacity:\n",
    "            return -1\n",
    "        items.sort(key=lambda x:x[1]/x[0])\n",
    "        res = 0\n",
    "        for p,w in items:\n",
    "            if capacity>=w:\n",
    "                capacity -= w\n",
    "                res+=p\n",
    "            else:\n",
    "                res += capacity * (p/w)\n",
    "                break\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
